"""
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import List


class Solution:
    """只要遍历到的都标记上
    """

    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        visited = [([False] * n) for i in range(m)]

        def valid_area(x: int, y: int):
            # 是否是合法的坐标
            return x >= 0 and y >= 0 and x < m and y < n
        ans = 0

        def backtrack(x, y):
            if grid[x][y] == "1" and not visited[x][y]:
                visited[x][y] = True
                for i in d:
                    new_x = x+i[0]
                    new_y = y+i[1]
                    if valid_area(new_x, new_y):
                        backtrack(new_x, new_y)
                return True

        
        for i in range(m):
            for j in range(n):
                if backtrack(i, j):
                    ans += 1
        return ans


if __name__ == "__main__":
    # islands = ["11110", "11010", "11000", "00000"]
    islands = ["11000", "11000", "00100", "00011"]
    res = Solution().numIslands(islands)
    print(res)
